package test.day09;

import java.util.*;

/**
 * 合并区间
 */
public class MergeIntervals {
	public int[][] merge(int[][] intervals) {
		List<int[]> res = new LinkedList<>();
		Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));

		int start = intervals[0][0];
		for (int i = 1; i < intervals.length; i++) {
			if (intervals[i][0] > intervals[i - 1][1]) {
				res.add(new int[]{start, intervals[i - 1][1]});
				start = intervals[i][0];
			} else {
				intervals[i][1] = Math.max(intervals[i][1], intervals[i - 1][1]);
			}
		}
		res.add(new int[]{start, intervals[intervals.length - 1][1]});
		return res.toArray(new int[res.size()][]);
	}

	public int[][] merge1(int[][] intervals) {
		BitSet bitSet = new BitSet();
		int max = 0;
		for (int[] interval : intervals) {
			int temp = interval[1] * 2 + 1;
			bitSet.set(interval[0] * 2, temp, true);
			max = temp >= max ? temp : max;
		}

		int index = 0, count = 0;
		while (index < max) {
			int start = bitSet.nextSetBit(index);
			int end = bitSet.nextClearBit(start);

			int[] item = {start / 2, (end - 1) / 2};
			intervals[count++] = item;

			index = end;
		}
		int[][] ret = new int[count][2];
		for (int i = 0; i < count; i++) {
			ret[i] = intervals[i];
		}

		return ret;
	}

	private int[][] merge2(int [][]arr) {
		if(arr == null || arr.length<=1) {
			return arr;
		}
		List<int[]> list = new ArrayList<>();
		Arrays.sort(arr,(a,b)->a[0]-b[0]);
		//按照两个组的左面的数进行比较
		//[1,3]   [2,4]  比较1和2     小的排前面，大的排后面
		Arrays.sort(arr,new Comparator<int[]>(){
			@Override
			public int compare(int[] a,int[] b){
				return a[0]-b[0];
			}
		});
		int i=0;
		int n = arr.length;
		while(i<n){
			int left = arr[i][0];
			int right = arr[i][1];
			while(i<n-1 && right>=arr[i+1][0]){
				right = Math.max(right, arr[i+1][1]);
				i++;
			}
			list.add(new int[] {left, right});
			i++;
		}
		return list.toArray(new int[list.size()][2]);
	}
}
